/*
 *     Os02Idea.java  Copyright (c) 2021. cc01cc. All rights reserved.
 *
 *     This file is part of os-02.
 *
 *     os-02 is free software: you can redistribute it and/or modify
 *     it under the terms of the GNU Affero General Public License as published
 *     by the Free Software Foundation, either version 3 of the License, or
 *     (at your option) any later version.
 *
 *     os-02 is distributed in the hope that it will be useful,
 *     but WITHOUT ANY WARRANTY; without even the implied warranty of
 *     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *     GNU Affero General Public License for more details.
 *
 *     You should have received a copy of the GNU Affero General Public License
 *     along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

import org.jetbrains.annotations.NotNull;
import java.util.*;

/**
 * Simulate page replacement, contains optimal, FIFO, LRU, LFU algorithms
 * @author cc01cc
 */
public class Os02Idea {
    public static void main(String[] args) {

        System.out.println(
            "Wait for while, please. \n"
            + "Reference string is initialing..."
            );
        referenceStringInitial();

        Scanner input = new Scanner(System.in);
        System.out.println(
            "Please enter the algorithm you want to choose \n"
            + "(1.Optimal 2.FIFO 3.LRU 4.LFU): "
            );
        int methodChoice = input.nextInt();
        System.out.println("Please enter the size of physical block: ");
        int physicalBlockSize = input.nextInt();
        input.close();

        double hitRate = 0.0;
        switch (methodChoice) {
            case 1:
                hitRate = optimal(
                    physicalBlockSize, 
                    referenceString, 
                    referenceStringSize
                    );
                System.out.println(
                    "Optimal algorithm's hit rate is: " 
                    + String.format("%.2f",hitRate)
                    );
                break;
            case 2:
                hitRate = fifo(
                    physicalBlockSize, 
                    referenceString
                    );
                System.out.println(
                    "FIFO algorithm's hit rate is: " 
                    + String.format("%.2f",hitRate)
                    );
                break;
            case 3:
                hitRate = lru(
                    physicalBlockSize, 
                    referenceString
                    );
                System.out.println(
                    "LRU algorithm's hit rate is: " 
                    + String.format("%.2f",hitRate)
                    );
                break;
            case 4:
                hitRate = lfu(
                    physicalBlockSize, 
                    referenceString, 
                    referenceStringSize
                    );
                System.out.println(
                    "LFU algorithm's hit rate is: " 
                    + String.format("%.2f",hitRate)
                    );
                break;
            default:
                System.out.println("There is no such algorithm!");
        }
    }
//    static double missCount = 0.0;
    /**
     * referenceString 页面号引用串
     * referenceStringSize 页面号引用串的大小
     */
    static ArrayList<Integer> referenceString;
    static int referenceStringSize;
    /**
     * 初始化页面引用串
     * @author cc01cc
     */
    public static void referenceStringInitial(){
        referenceString = new ArrayList<>();
        Collections.addAll(
            referenceString, 
            7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 
            0, 3, 2, 1, 2, 0, 1, 7, 0, 1
            );
        referenceStringSize = 8;
    }

    /**
     * 最佳置换
     * @param physicalBlockSize 物理块数量
     * @param referenceString 页面引用串
     * @param referenceStringSize 页面引用串取值大小
     * @return 命中率
     * @author cc01cc
     */
    public static double optimal(
        int physicalBlockSize, 
        @NotNull ArrayList<Integer> referenceString, 
        int referenceStringSize
        ) {
        Set<Integer> memory = new HashSet<>();
        double missCount = 0.0;
        for(int i = 0; i < referenceString.size(); i++) {
            if(!memory.contains(referenceString.get(i))) {
                if(memory.size() == physicalBlockSize){
                    missCount++;
                    // 统计内存中引用串下次访问距离
                    // stringInMemoryCount[] 存储引用串下次访问距离；
                    // index为引用串的值；
                    // stringInMemoryCount[index] 为当前引用串所对应的距离下次访问的值；不在内存中的值为0；
                    int[] stringInMemoryCount = new int[referenceStringSize];
                    //stringInMemory 存储内存中的引用串值
                    for(int stringInMemory : memory){
                        // 初始赋值为 1，即包含下一个相同索引
                        // 也避免值为0，在后边被直接移除
                        stringInMemoryCount[stringInMemory] = 1;
                        // 在没有碰到下一个相同的引用串前，进行累加
                        for(int j = i+1; j < referenceString.size(); j++){
                            if(referenceString.get(j) != stringInMemory){
                                stringInMemoryCount[stringInMemory]++;
                            }else{
                                break;
                            }
                        }
                    }

                    // 比较并选择内存中引用串距离下次访问最久的
                    // maxUse 定义最远距离的引用串
                    int maxUse = -1;
                    for(int stringInMemory : memory){
                        //maxUse 赋予初始值，防止-1作数组指引时越界
                        if(maxUse == -1){
                            maxUse = stringInMemory;
                        }
                        // 如果值为0，则直接移除，并退出循环
                        if(stringInMemoryCount[stringInMemory] == 0){
                            memory.remove(stringInMemory);
                            break;
                        }else{
                            // 如果当前引用串的值比maxUse引用串的值大，则进行赋值
                            if (
                                stringInMemoryCount[stringInMemory] 
                                > stringInMemoryCount[maxUse]
                                ){
                                maxUse = stringInMemory;
                            }
                        }
                    }

                    // 当内存为满时，移除maxUse
                    // 主要是防止，stringInMemory值为0时被移除后，这儿再被移除
                    if(memory.size() == physicalBlockSize){
                        memory.remove(maxUse);
                    }
                }
                memory.add(referenceString.get(i));
            }
        }
        System.out.println(
            "The number of page replacement is: " 
            + String.format("%.0f",missCount)
            );
        return 1-(missCount/referenceString.size());
    }

    /**
     * 先进先出
     * @param physicalBlockSize 物理块数量
     * @param referenceString 页面引用串
     * @return 命中率
     * @author cc01cc
     */
    public static double fifo(
        int physicalBlockSize, 
        @NotNull ArrayList<Integer> referenceString
        ) {
        Queue<Integer> memory = new LinkedList<>();
        double missCount = 0.0;
        for (Integer referenceStringUtil : referenceString) {
            if (!memory.contains(referenceStringUtil)) {
                if (memory.size() == physicalBlockSize) {
                    missCount++;
                    memory.poll();
                }
                memory.offer(referenceStringUtil);
            }
        }
        System.out.println(
            "The number of page replacement is: " 
            + String.format("%.0f",missCount)
            );
        return 1-(missCount/referenceString.size());
    }

    /**
     * 最近最久未使用
     * @param physicalBlockSize 物理块数量
     * @param referenceString 页面引用串
     * @return 命中率
     * @author cc01cc
     */
    public static double lru( 
        int physicalBlockSize, 
        @NotNull ArrayList<Integer> referenceString
        ){
        Queue<Integer> memory = new LinkedList<>();
        double missCount = 0.0;
        for (Integer referenceStringUtil : referenceString) {
            if (
                !memory.contains(referenceStringUtil) 
                && memory.size() == physicalBlockSize
                ) {
                // 当内存满的时候，且不包含引用值时，
                missCount++;
                // 弹出最先进入的值，推入新值
                memory.poll();
                memory.offer(referenceStringUtil);
            } else if (memory.contains(referenceStringUtil)) {
                // 当内存包含引用值时
                // 将引用值换到最新的位置
                memory.remove(referenceStringUtil);
                memory.offer(referenceStringUtil);
            } else{
                // 当内存未满的时候
                // 添加引用值
                memory.offer(referenceStringUtil);
            }
        }
        System.out.println(
            "The number of page replacement is: " 
            + String.format("%.0f",missCount)
            );
        return 1-(missCount/referenceString.size());
    }

    /**
     * 最少使用
     * @param physicalBlockSize 物理块数量
     * @param referenceString 页面引用串
     * @param referenceStringSize 页面引用串取值大小
     * @return 命中率
     * @author cc01cc
     */
    public static double lfu ( 
        int physicalBlockSize, 
        @NotNull ArrayList<Integer> referenceString, 
        int referenceStringSize 
        ) {
        double missCount = 0.0;
        Set<Integer> memory = new HashSet<>();
        int[] useCount = new int[referenceStringSize];
        for(Integer referenceStringUtil : referenceString){
            useCount[referenceStringUtil] ++;
            // memory 不包含 referenceStringUtil
            if(
                !memory.contains(referenceStringUtil)
                &&memory.size() == physicalBlockSize
                ){
                int minUse = -1;
                missCount++;
                for(Integer stringInMemory : memory){
                    if(minUse == -1){
                        minUse = stringInMemory;
                    }
                    if(useCount[stringInMemory] < useCount[minUse]){
                        minUse = stringInMemory;
                    }
                }
                memory.remove(minUse);
            }
            memory.add(referenceStringUtil);
        }
        System.out.println(
            "The number of page replacement is: " 
            + String.format("%.0f",missCount)
            );
        return 1-(missCount/referenceString.size());
    }
}